package cn.zzf.algs.note.base.util;

import cn.zzf.algs.note.base.sort.Sort;
import edu.princeton.cs.algs4.StdRandom;
import org.springframework.util.StopWatch;

import java.math.BigDecimal;
import java.util.Random;

/**
 * 排序算法的工具类
 * @author GaoFeng2017
 * @date 2020/6/16 10:32
 */
public class SortUtil {


    /**
     * a is less than b?
     */
    @SuppressWarnings("unchecked")
    public static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }


    /**
     * a is greater than b
     */
    @SuppressWarnings("unchecked")
    public static boolean greater(Comparable a, Comparable b) {
        return !lessAndEqual(a, b);
    }


    @SuppressWarnings("unchecked")
    /** a is less than equals b ?   */
    public static boolean lessAndEqual(Comparable a, Comparable b) {
        return a.compareTo(b) <= 0;
    }

    @SuppressWarnings("unchecked")
    /** a is equals b */
    public boolean equal(Comparable a, Comparable b) {
        return a.compareTo(b) == 0;
    }

    /**
     * 交换数组中两个元素
     */
    public static void exchange(Comparable[] elements, int aIndex, int bIndex) {
        Comparable temp = elements[aIndex];
        elements[aIndex] = elements[bIndex];
        elements[bIndex] = temp;
    }

    /**
     * 打印数组
     */
    public static void printArray(Comparable[] elements) {

        StringBuilder sb = new StringBuilder();
        sb.append("[");

        for (Comparable element : elements) {
            sb.append(element).append(", ");
        }

        sb.delete(sb.length() - 2, sb.length());
        sb.append("]");

        System.out.println(sb.toString());

    }

    /**
     * 判断一个数组是否从小到大排序
     */
    @SuppressWarnings("unchecked")
    public static <T> boolean isSorted(Comparable[] elements) {
        for (int i = 0; i < elements.length - 1; i++) {
            if (elements[i].compareTo(elements[i + 1]) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 根据给定的长度生成随机数组，使用均匀分布
     */
    public static Integer[] generateRandomNumbers(int size) {
        Random random = new Random();
        Integer[] numbers = new Integer[size];
        int baseNum = size * 100;

        for (int i = 0; i < size; i++) {
            numbers[i] = random.nextInt(baseNum);
        }

        return numbers;

    }

    /**
     * 生成随机数，使用泊松分布
     */
    public static Integer[] generateRandomNumbersWithGaussianDistribution(int size) {

        Integer[] numbers = new Integer[size];
        int baseNum = size * 100;

        for (int i = 0; i < size; i++) {
            numbers[i] = (int) (StdRandom.gaussian() * baseNum);
        }

        return numbers;
    }

    public static Integer[] generateRandomNumbersWithPoissonDistribution(int size) {
        Integer[] numbers = new Integer[size];
        int baseNum = size * 100;

        for (int i = 0; i < size; i++) {
            numbers[i] = StdRandom.poisson(2) * baseNum;
        }

        return numbers;

    }


    /**
     * 根据给定的比例和大小，生成一个长度为elementsSize，且有序比例为orderedRatio的随机数组
     */
    public static Integer[] generateRandomNumbersWithPartiallyOrdered(int elementsSize, float orderedRatio) {

        Integer[] result = new Integer[elementsSize];

        // 长度为1的元素数组特殊处理
        if (elementsSize == 1) {
            return new Integer[]{new Random().nextInt(elementsSize)};
        }

        // 有序的数量
        BigDecimal elementsBigDecimal = new BigDecimal(String.valueOf(orderedRatio));
        int orderedSize = new BigDecimal(elementsSize)
                .multiply(elementsBigDecimal)
                .divide(new BigDecimal("100.00"), 0, BigDecimal.ROUND_HALF_UP).intValue();

        // 如果有序列长度为1
        if (orderedSize == 1) {
            orderedSize = 2;
        }

        // 是否为奇数个的有序元素
        boolean isOddOrderSize = (orderedSize & 1) == 1;

        // 无序的数量
        int disorderSize = elementsSize - orderedSize;

        // 几率发生器
        Random orderRandom = new Random();

        // 当前元素有序和无序的概率
        int probability = 50;
        int lessValue = elementsSize - 1;
        int greaterValue = elementsSize;

        // 打印有序元素的数量和无序元素的数量
        System.out.println("orderedSize: " + orderedSize + ", disorderSize: " + disorderSize);
        result[0] = greaterValue++;

        boolean isUnFinishedGenerateDisorderElements = disorderSize > 0;
        boolean isGenerateOrderedElement = (isUnFinishedGenerateDisorderElements && isGenerateOrderedElement(orderRandom, probability));
        boolean isLastElementOrdered = false;
        boolean isHasEnoughLength = result.length - disorderSize - 1 > 3;
        int startIndex = 1;


        // 生成第一组元素，可能有序可能无序（这样不用单独处理disorderSize为1）;
        if (isGenerateOrderedElement) {
            disorderSize--;
        } else {
            int value;
            startIndex = 2;
            if (isOddOrderSize) {
                if (!isHasEnoughLength) {
                    startIndex = 3;
                } else {
                    if (orderedSize == 3 || isGenerateOrderedElement(orderRandom, probability)) {
                        startIndex = 3;
                    }
                }
            }

            System.out.println("startIndex:" + startIndex);
            for (int i = 1; i < startIndex; i++) {
                value = greaterValue++;
                result[i] = value;
            }

            orderedSize -= startIndex;
            isLastElementOrdered = true;
        }

        // 第一个或者第一对元素后的生成
        for (int i = startIndex; i < elementsSize; i++) {

            int value;
            isUnFinishedGenerateDisorderElements = disorderSize > 0;
            boolean isFinishedGenerateOrderElements = orderedSize <= 0;
            isGenerateOrderedElement = isUnFinishedGenerateDisorderElements
                    && isGenerateOrderedElement(orderRandom, probability);
            // System.out.println(Arrays.toString(result));

            if (isGenerateOrderedElement || isFinishedGenerateOrderElements) {
                result[i] = lessValue--;
                disorderSize--;
                isLastElementOrdered = false;
               /* System.out.println("in disorder, orderSize: " + orderedSize + ",disorderSize: " + disorderSize +
                        ", i: " + i + ", length: " + 1 + ", result: " + Arrays.toString(result) + ", isLastElementsSorted: " + isLastElementOrdered);*/
            } else {

                // 有序和无序的情况
                int length = 1;
                // 前一个元素是无序的，必须先产生一个无序的元素，否则前一个无序的元素会变成有序的元素
                if (!isLastElementOrdered || orderedSize == 2) {

                    isOddOrderSize = (orderedSize & 1) == 1;
                    isHasEnoughLength = result.length - disorderSize - i > 3;

                    if (isOddOrderSize && !isHasEnoughLength) {
                        length = 2;
                    }

                    result[i++] = lessValue--;
                    orderedSize--;

                }


                /*System.out.println("in order, orderSize: " + orderedSize + ",disorderSize: " + disorderSize +
                        ", i: " + i + ", length: " + length + ", result: " + Arrays.toString(result) + ", isLastElementsSorted: " + isLastElementOrdered);*/

                for (int j = i; j < i + length; j++) {
                    value = greaterValue++;
                    result[j] = value;
                }

                orderedSize -= length;
                i = i + length - 1;
                isLastElementOrdered = true;
            }
        }

        return result;
    }

    private static boolean isGenerateOrderedElement(Random orderedRandom, int probability) {
        int orderedRandomValue = orderedRandom.nextInt(probability + probability);
        return orderedRandomValue >= probability;
    }

    /**
     * 根据比例和大小生成部分有序的数据
     */
    /*public static void generateRandomNumbersWithPartiallyOrdered(int elementsSize, float orderedRatio) {

        Integer[] result = new Integer[elementsSize];
        int maxValue = elementsSize * 100;
        int orderedSize = Math.min((int) (orderedRatio * elementsSize), elementsSize) - 1;
        int maxOrderedSizeWithOnceGenerate = orderedSize / 4;
        int randomSize = elementsSize - orderedSize;
        int maxRandomSize = randomSize / 4;

        Random random = new Random();
        result[0] = random.nextInt(maxValue);
        int currentMaxOrderedSize = Math.max(1, random.nextInt(maxOrderedSizeWithOnceGenerate));

        for (int i = 1; i < elementsSize; i++) {
            if (orderedSize > 0) {
                if (currentMaxOrderedSize > 0) {
                    int value;

                    do {
                        value = random.nextInt(maxValue);
                    } while (SortUtil.less(result[i - 1], value));

                    result[i] = value;
                    orderedSize--;
                    currentMaxOrderedSize--;
                } else {
                    int currentRandomSize = Math.max(random.nextInt(maxRandomSize), 1);
                    for (int j = i; j < i + currentRandomSize; j++) {
                        result[i] = random.nextInt(maxValue);
                    }
                    currentMaxOrderedSize = random.nextInt(maxOrderedSizeWithOnceGenerate);
                }
            } else {
                result[i] = random.nextInt(maxValue);
            }

        }

    }*/

    /**
     * 排序测试，自动生成给定长度的随机数字数组进行排序，排序后测试排序的正确性，同时打印排序过程中信息。
     */
    public static <T extends Sort> void testSort(Class<T> sortClass, int elementSize) {
        Integer[] numbers = SortUtil.generateRandomNumbers(elementSize);
        testSort(sortClass, numbers);
    }

    private static <T extends Sort> void testSort(Class<T> sortClass, Integer[] numbers) {

        System.out.println("====== start test " + sortClass.getSimpleName() + " ======\n");

        T t = null;

        try {
            t = sortClass.newInstance();
        } catch (InstantiationException | IllegalAccessException e) {
            e.printStackTrace();
        }

        boolean isSmallData = numbers.length <= 100;
        System.out.println("elements size is " + numbers.length);

        if (isSmallData) {
            System.out.println("before sort");
            SortUtil.printArray(numbers);
        }

        // 开启性能监控
        StopWatch stopWatch = new StopWatch();
        stopWatch.start("start " + sortClass.getSimpleName());
        t.sort(numbers);
        stopWatch.stop();

        if (isSmallData) {
            System.out.println("after sort");
            SortUtil.printArray(numbers);
        }

        boolean sorted = SortUtil.isSorted(numbers);
        System.out.println("numbers is sorted? " + sorted);
        assert sorted;
        System.out.println(stopWatch.prettyPrint());

        System.out.println("====== end test " + sortClass.getSimpleName() + " ======\n");
    }


    /**
     * 对于同一个数据源, 使用不同的排序算法，进行排序性能测试
     */
    public static void testSortPerformance(int elementSize, Class<? extends Sort>... sortClasses) {
        // 生成测试数据
        Integer[] numbers = SortUtil.generateRandomNumbers(elementSize);

        // 打印区分度
        System.out.println("the elements order degree is " + SortUtil.orderDegree(numbers));

        // 遍历排序
        for (Class<? extends Sort> sortClass : sortClasses) {
            SortUtil.testSort(sortClass, SortUtil.cloneArray(numbers));
        }
    }

    private static Integer[] cloneArray(Integer[] srcArray) {
        Integer[] destArray = new Integer[srcArray.length];
        System.arraycopy(srcArray, 0, destArray, 0, srcArray.length);
        return destArray;
    }

   /* public static int orderDegree(Integer[] numbers) {
        int result = 0;
        // 获取数组的区分度
        for (int i = 1; i < numbers.length; i++) {
            // 前一个元素比后一个元素大，则==1
            if (SortUtil.less(numbers[i], numbers[i - 1])) {
                result++;
            }
        }
        return result;
    }
    */

    // step

    public static int orderDegree(Integer[] numbers) {


        if (numbers.length == 1) {
            return 1;
        }
        // isLast
        boolean isLastElementOrdered = false;
        int result = 0;

        for (int i = 1; i < numbers.length; i++) {
            if (SortUtil.less(numbers[i], numbers[i - 1])) {
                isLastElementOrdered = false;
            } else {
                // 7 * 0.4 = 2.8
                if (isLastElementOrdered) {
                    result++;
                } else {
                    result += 2;
                    isLastElementOrdered = true;
                }
            }
        }

        return result;

    }
}
